package com.example.recursion;

/**
 * @Date 2022/7/9
 * @Created by Jonathan
 */
public class Knapsack {
    public static void main(String[] args) {
        // getResult()
    }


    public static int getResult(int[] w, int[] v, int bag) {
        return process(w, v, 0, bag);
    }


    public static int process(int[] w, int[] v, int index, int rest) {
        if (rest < 0) {  // base case
            return -1;
        }
        if (index == w.length) {
            return 0;
        }
        // 不要index所在位置的货物
        int p1 = process(w, v, index + 1, rest);

        int p2 = -1;
        // 要了index所在位置的获取
        int pNext = process(w, v, index + 1, rest - w[index]);
        if (pNext != -1) {
            p2 = pNext + v[index];
        }
        return Math.max(p1, p2);
    }

}
